package huawei.window;

public class J424 {
    public static void main(String[] args) {
        System.out.println(characterReplacement("ABAB",2));
        System.out.println(characterReplacement("AABABBA",1));
    }
    public static int characterReplacement(String s, int k) {
        /**
         * 思路: 允许改动k次,即,最多存在k个不同字符.
         * 优化思路:TODO
         * 我的思路:当窗口不满足k个不同字母的时候,left++,直到满足条件
         * 题解思路: 不考虑窗口收缩情况,因为求解是最长窗口.从满足条件的情况收缩,必然不是最长窗口.
         * 此时left++,right++,直到找到新的符合条件窗口继续增长,不然这昂的差值维持的结束,
         * 最终最大窗口就是 right-left+1.
         */
        int left = 0;
        int right =0;
        int maxLen =0;
        int[] cache =new int[26];
        for ( ; right < s.length(); right++) {
            cache[s.charAt(right)-'A']++;
            int maxIndex=0;
            for (int i = 0; i < 26; i++) {
                if(cache[maxIndex]<cache[i]){
                    maxIndex=i;
                }
            }
            int diff = right-left+1-cache[maxIndex];
            while (diff>k){
                cache[s.charAt(left)-'A']--;
                left++;
                // 只有减少的是最长字符的字母,才需要重新统计
                if(s.charAt(left-1)==s.charAt(maxIndex)){
                     maxIndex=0;
                    for (int i = 0; i < 26; i++) {
                        if(cache[maxIndex]<cache[i]){
                            maxIndex=i;
                        }
                    }
                     diff = right-left+1-cache[maxIndex];
                }else {
                    diff--;
                }
            }
            maxLen=Math.max(maxLen,right-left+1);

        }
        return maxLen;
    }
}
